#ifndef _SDRADIX_SORT_H
#define _SDRADIX_SORT_H
#include <cstdlib>
#include <cstring>

/*******************************************************+ 
 * Based on Radix Sorting - LSD Technique               *
 * Its primarily used for unsigned integer datatype              *
 * O(n) sorting                                         *
 +******************************************************/

namespace stdds {
	template<typename T>
		class RadixSort {
		};

	/* template specialization for unsigned int */
	template <>
		class RadixSort<unsigned int> {
		public:
			unsigned int *mSrc;
			unsigned int mLen;

			RadixSort(unsigned int *pSrc,unsigned int pLen):mSrc(pSrc),mLen(pLen){}

			unsigned int& operator[] (unsigned int i){return mSrc[i];}

			void sort() {
				unsigned int *tDst = (unsigned int*)malloc(sizeof(unsigned int)*mLen);

				print(mSrc,mLen);
				radix_sort(mSrc,tDst,mLen);
				free(tDst);
			}

			void radix_sort(unsigned int *src,unsigned int *dest,unsigned int pLen) {
				unsigned int mask = 0xFF;
				for(unsigned int j=sizeof(unsigned int);j!=0;j--){
					unsigned int count[256];
					unsigned int index[256];
					unsigned int lShift=(j-1)*8;
					unsigned int rShift=8*(sizeof(unsigned int)-1);

					for(unsigned int i=0;i<256;i++) count[i]=0;

					for(unsigned int i=0;i<pLen;i++)
						count[((src[i]&mask)<<lShift)>>rShift]++;

					index[0]=0;
					for(unsigned int i=1;i<256;i++) 
						index[i]=index[i-1]+count[i-1];

					for(unsigned int i=0;i<pLen;i++)
						dest[index[((src[i]&mask)<<lShift)>>rShift]++]=src[i];

					for(unsigned int i=0;i<pLen;i++) src[i]=dest[i];

					print(dest,pLen);
					mask=(mask<<8);
				}
			}

			void print(unsigned int *pSrc,unsigned int pLen) {
				for(unsigned int i=0;i<pLen;i++){std::cout<<pSrc[i]<<" ";}
				std::cout<<std::endl;
			}

		};
}


#endif
